#include <bits/stdc++.h>
#include <numeric>  // 包含 std::reduce
#include <functional>  // 包含 std::bit_or
using namespace std;

/*
2044. 统计按位或能得到最大值的子集数目
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。

对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。

 

示例 1：

输入：nums = [3,1]
输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]
示例 2：

输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。
示例 3：

输入：nums = [3,2,1,5]
输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]
 

提示：

1 <= nums.length <= 16
1 <= nums[i] <= 105
*/

// 法一
class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int max_or = 0;
        // 最大位或
        for (int num : nums)    max_or |= num;

        int count = 0;  // 计数器
        // 从0开始回溯 初始当前为0
        backTrack(nums, 0, 0, max_or, count);
        return count;
    }

    // 所有可能的子集 计算按位或统计符合条件子集
    void backTrack(vector<int>& nums, int idx, int cur_or, int max_or, int &count) {
        // 所有元素都处理完毕
        if (idx == nums.size()) {
            // 当前子集的按位或 等于最大max_or count+1
            if (cur_or == max_or)   count++;
            return;
        }

        // 两种情况 当前元素加入子集
        // 要计算按位或结果 cur_or | nums[idx]   继续idx+1
        backTrack(nums, idx + 1, cur_or | nums[idx], max_or, count);
        // 不选择当前元素
        backTrack(nums, idx + 1, cur_or, max_or, count);
    }
};

// 法二
class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        // 计算所有元素的按位或总和（最大可能的按位或值）
        // 使用标准库的reduce配合bit_or完成累积按位或操作
        int total_or = reduce(nums.begin(), nums.end(), 0, bit_or());
        int ans = 0;      // 存储符合条件的子集数量
        int n = nums.size(); // 数组长度

        // 定义递归lambda函数进行深度优先搜索
        // 参数：i-当前处理的元素索引，subset_or-当前子集的按位或值
        auto dfs = [&](auto&& self, int i, int subset_or) -> void {
            // 剪枝优化：若当前子集的按位或已达到最大值
            // 剩余 (n - i) 个元素每个都有选/不选两种可能，共 2^(n-i) 种组合
            if (subset_or == total_or) {
                ans += 1 << (n - i);  // 位运算计算 2 的 (n-i) 次方
                return;
            }
            // 终止条件：所有元素已处理完毕
            if (i == n) {
                return;
            }
            
            // 分支 1：不选择当前第 i 个元素，递归处理下一个
            self(self, i + 1, subset_or);
            
            // 分支 2：选择当前第 i 个元素，更新按位或后递归处理下一个
            self(self, i + 1, subset_or | nums[i]);
        };

        // 从第 0 个元素开始递归，初始子集按位或为 0
        dfs(dfs, 0, 0);
        return ans;
    }
};